package xyz.xiaotugou.dataStructure.basic;

/**
 * @author ysy
 * @version 1.0
 * @Title: 自定义跳表
 *          - 应用场景：redis中
 *          - 设计初衷：基于链表LinkedList，优化查询的时间复杂度 【O(n) -> O(log n)】
 *          - 弊端：
 *              - 增、删的时间复杂度【O(1) -> o(log n)】
 *              - 增、删元素之后，索引的步长会不工整
 *              - 空间复杂度为O(n)
 *          - 设计原理：【升维：空间换时间】添加多级索引
 *              - 1级索引:n/2、2级索引:n/4、3级索引:n/8 、 …… 、k级索引:n/(2^k)
 *              - 若索引为k级时，最高级的索引有2个节点，即 n/(2^k)=2 , 故 k = log2(n)-1
 *
 *              https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html 【跳表的实现】
 *              https://www.zhihu.com/question/20202931 （为什么redis使用跳表，而不是红黑树）
 *
 * @Note <b>ProjectName:</b> Pre-research
 * <br><b>PackageName:</b> xyz.xiaotugou.dataStructure.basic
 * <br><b>ClassName:</b> MySkipList
 * <br><b>Date:</b> 2022/1/5 22:23
 */
public class MySkipList {

}
